// https://www.lintcode.com/problem/backpack/

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int[] c = new int[m + 1]; // c[i]代表容量最大为i能装多少
        Arrays.fill(c, 0);
        if (A.length > 0) {
            for (int i = 0; i < A.length; ++i) {
                for (int j = m; j >= A[i]; --j) {
                    c[j] = Math.max(c[j - A[i]] + A[i], c[j]);
                }
            }
        }
        return c[m];
    }
}